package GreedyAlgorithmPackage;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * @author Lzm
 * @version 1.0
 */
public class largestSumAfterKNegations_ {
  @Test
  public void largestSumAfterKNegationsTest(){
    //int[] nums = new int[]{4,2,3};
    //int[] nums = new int[]{3,-1,0,2};
    int[] nums = new int[]{2,-3,-1,5,-4};
    System.out.println(largestSumAfterKNegations(nums,2));
  }
  public int largestSumAfterKNegations(int[] nums, int k) {
    Arrays.sort(nums);
    if (k % 2 == 0 && nums[0] >= 0){
      return getSum(nums);
    }
    else if(k % 2 != 0 && nums[0] >= 0){
      nums[0] = -nums[0];
      return getSum(nums);
    }
    else if (nums[0] < 0){
      int index = getIntIndex(nums);
      for (int i = 0 ; i < index ; i++){
        nums[i] = -nums[i];
        k--;
        if (k == 0){
          return getSum(nums);
        }
      }
      Arrays.sort(nums);
      if (k % 2 == 0){
        return getSum(nums);
      }
      else if(k % 2 != 0){
        nums[0] = -nums[0];
        return getSum(nums);
      }
      return getSum(nums);
    }
    return getSum(nums);
  }
  public int getSum(int[] nums){
    int sum = 0;
    for (int i= 0 ; i < nums.length ; i++){
      sum += nums[i];
    }
    return sum;
  }
  /*得到顺序数组的正数分界索引*/
  public int getIntIndex(int[] nums){
    int index = 0;
    for (int i = 0 ; i < nums.length ; i++){
      if (nums[i] < 0){
        index++;
      }
      else{
        return index;
      }
    }
    return index;
  }
}
